package review;

import java.util.ArrayList;
import java.util.List;

import data_structure.BTNode;

public class LeetCode_day12_tree_review {

	/**
	 * Given an array without duplicates, return the root of all possible trees
	 * @param a
	 * @return
	 */
	public static List<BTNode> uniqueBinarySearchTreesII(int[] a){
		if(a == null) return null;
		return constructTrees(a, 0, a.length-1);
	}
	
	public static List<BTNode> constructTrees(int[] a, int start, int end){
		List<BTNode> res = new ArrayList<BTNode>();
		if(start <= end){
			for(int i = start ; i <= end ; i++){//for every possible root
				List<BTNode> leftSubtree = constructTrees(a, start, i-1);
				List<BTNode> rightSubtree = constructTrees(a, i+1, end);
				for(BTNode left : leftSubtree)
					for(BTNode right : rightSubtree){
						BTNode root = new BTNode(a[i]);
						root.left = left;
						root.right = right;
						res.add(root);
					}
			}
		}else res.add(new BTNode(null));//necessary
		//else if(start == end) res.add(new BTNode(a[start]));
		return res;
	}
	
	/**
	 * From preorder, we find root
	 * From inorder, we find the left subtree range and right subtree range
	 * @param preorder
	 * @param inorder
	 * @return
	 */
	public static BTNode constructBTFromPreorderInorder(int[] preorder, int[] inorder){
		if(preorder == null || inorder == null) return null;
		return constructBTFromPreIn(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
	} 
	
	public static BTNode constructBTFromPreIn(int[] pre, int[] in, int prestart, int preend, int instart, int inend){
		if(prestart < 0 || prestart >= pre.length || instart < 0 || inend >= pre.length) return null;
		BTNode root = new BTNode(pre[prestart]);
		if(prestart < preend && instart < inend){
			//leftsubtree
			int leftLength = 0;
			for(int i = instart ; i <= inend ; i++){
				leftLength++;
				if(in[i] == pre[prestart]) break;
			}
			leftLength--;
			root.left = constructBTFromPreIn(pre, in, prestart+1, prestart+leftLength-1, instart, instart+leftLength-1);
			root.right = constructBTFromPreIn(pre, in, prestart+leftLength, preend, instart+leftLength+1, inend);
		}
		return root;
	}
	
	public static void constructBTFromPostorderInorder(){
		
	}
	
	public static void recoveryBST(BTNode root, BTNode[] res){
		if(res[0] == null || res[1] == null){
			double value = root.val.doubleValue();
			if(root.left != null){
				if(root.left.val.doubleValue() > value)
					if(res[0] == null) res[0] = root;
					else res[1] = root;
				recoveryBST(root.left, res);
			}
			if(root.right != null){
				if(root.right.val.doubleValue() < value)
					if(res[0] == null) res[0] = root;
					else res[1] = root;
				recoveryBST(root.right, res);
					
			}
		}else{//swap
			Number temp = res[0].val;
			res[0].val = res[1].val;
			res[1].val = temp;
		}
	}
	
	public static BTNode findInorderSuccessor(BTNode node, BTNode root){
		BTNode res = null;
		if(node == null) return res;
		if(node.right != null){
			res = node.right;
			while(res.left != null) res = res.left;
		}else{
			BTNode ind = root;
			if(node == ind) return res;
			while(ind != node){
				if(node.val.doubleValue() < ind.val.doubleValue()){
					res = ind;
					ind = ind.left;
				}else if(node.val.doubleValue() > ind.val.doubleValue()) ind = ind.right;
				else break;
			}
		}
		return res;
	}
	
	public static void findHeightOfTree(BTNode root){
		
	}
	
	public static void main(String[] args) {
		System.out.println(uniqueBinarySearchTreesII(new int[]{1,2,3}).size());

	}

}